package cn.ac.cintcm.prespring.cluster.base;

/**
 * Longest Common String 
 * @author CaoMudan
 *
 */
public class LCS {
	public static int LCSlength(String s1, String s2) {
		char[] left = s1.toCharArray();
		char[] right = s2.toCharArray();
		int lenLeft = left.length;
		int lenRight = right.length;

		int[] c = new int[lenRight];
		//int start, end, len;
		int len=0;
		//end = len = 0;
		for (int i = 0; i < lenLeft; i++) {
			for (int j = lenRight - 1; j >= 0; j--) {
				if (left[i] == right[j]) {
					if (i == 0 || j == 0)
						c[j] = 1;
					else
						c[j] = c[j - 1] + 1;
				} else
					c[j] = 0;
				if (c[j] > len) {
					len = c[j];
					//end = j;
				}
			}
		}
		return len;
//		char[] p = new char[len];
//		start = end - len + 1;
//		for (int i = start; i <= end; i++)
//			p[i - start] = right[i];
//		return p;
	}

}
